class Node:
    """
    Node represents a node in the AVL tree.

    Attributes:
        data: Data stored in the node.
        left: Left child node.
        right: Right child node.
        height: Height of the node.
    """

    def __init__(self, data):
        """
        Initialize a Node with data.

        Args:
            data: Data for this node.
        """
        self.data = data
        self.left = None
        self.right = None
        self.height = 1

    def __repr__(self):
        """
        Returns a string that represents the node.

        Returns:
            A string representation of the node.
        """
        return f"Node({self.data})"


class AVLTree:
    """
    AVLTree represents an AVL tree data structure.

    Attributes:
        root: Root node of the AVL tree.
    """

    def __init__(self):
        """
        Initialize an empty AVL tree with no root node.
        """
        self.root = None

    def insert(self, data):
        """
        Insert a new node with the given data into the AVL tree.

        Args:
            data: Data for the new node.
        """
        self.root = self._insert_recursive(self.root, data)

    def _insert_recursive(self, current_node, data):
        """
        Recursive helper method to insert a new node into the AVL tree.

        Args:
            current_node: Current node being visited.
            data: Data for the new node.

        Returns:
            Updated node after insertion.
        """
        if current_node is None:
            return Node(data)

        if data < current_node.data:
            current_node.left = self._insert_recursive(current_node.left, data)
        else:
            current_node.right = self._insert_recursive(current_node.right, data)

        current_node.height = 1 + max(self._get_height(current_node.left), self._get_height(current_node.right))

        return self._balance(current_node, data)

    def _balance(self, node, data):
        """
        Perform balancing operations on a node in the AVL tree.

        Args:
            node: Node to balance.
            data: Data associated with the node.

        Returns:
            Balanced node.
        """
        balance_factor = self._get_balance_factor(node)

        # Left Left Case
        if balance_factor > 1 and data < node.left.data:
            return self._rotate_rr(node)

        # Right Right Case
        if balance_factor < -1 and data > node.right.data:
            return self._rotate_ll(node)

        # Left Right Case
        if balance_factor > 1 and data > node.left.data:
            return self._rotate_lr(node)

        # Right Left Case
        if balance_factor < -1 and data < node.right.data:
            return self._rotate_rl(node)

        return node

    def _rotate_ll(self, node):
        """
        Perform a left-left rotation in the AVL tree.

        Args:
            node: Node to be rotated.

        Returns:
            Rotated node.
        """
        new_root = node.right
        node.right = new_root.left
        new_root.left = node

        node.height = 1 + max(self._get_height(node.left), self._get_height(node.right))
        new_root.height = 1 + max(self._get_height(new_root.left), self._get_height(new_root.right))

        return new_root

    def _rotate_rr(self, node):
        """
        Perform a right-right rotation in the AVL tree.

        Args:
            node: Node to be rotated.

        Returns:
            Rotated node.
        """
        new_root = node.left
        node.left = new_root.right
        new_root.right = node

        node.height = 1 + max(self._get_height(node.left), self._get_height(node.right))
        new_root.height = 1 + max(self._get_height(new_root.left), self._get_height(new_root.right))

        return new_root

    def _rotate_lr(self, node):
        """
        Perform a left-right rotation in the AVL tree.

        Args:
            node: Node to be rotated.

        Returns:
            Rotated node.
        """
        node.left = self._rotate_ll(node.left)
        return self._rotate_rr(node)

    def _rotate_rl(self, node):
        """
        Perform a right-left rotation in the AVL tree.

        Args:
            node: Node to be rotated.

        Returns:
            Rotated node.
        """
        node.right = self._rotate_rr(node.right)
        return self._rotate_ll(node)

    def delete(self, data):
        """
        Delete a node with the given data from the AVL tree.

        Args:
            data: Data of the node to delete.
        """
        self.root = self._delete_recursive(self.root, data)

    def _delete_recursive(self, current_node, data):
        """
        Recursive helper method to delete a node from the AVL tree.

        Args:
            current_node: Current node being visited.
            data: Data of the node to delete.

        Returns:
            Updated node after deletion.
        """
        if current_node is None:
            return current_node

        if data < current_node.data:
            current_node.left = self._delete_recursive(current_node.left, data)
        elif data > current_node.data:
            current_node.right = self._delete_recursive(current_node.right, data)
        else:
            # Node to delete found
            if current_node.left is None:
                return current_node.right
            elif current_node.right is None:
                return current_node.left
            else:
                # Node has two children
                min_node = self._get_min_node(current_node.right)
                current_node.data = min_node.data
                current_node.right = self._delete_recursive(current_node.right, min_node.data)

        current_node.height = 1 + max(self._get_height(current_node.left), self._get_height(current_node.right))

        return self._balance(current_node, data)

    def search(self, data):
        """
        Search for a node with the given data in the AVL tree.

        Args:
            data: Data to search for.

        Returns:
            True if the node is found, False otherwise.
        """
        return self._search_recursive(self.root, data)

    def _search_recursive(self, current_node, data):
        """
        Recursive helper method to search for a node in the AVL tree.

        Args:
            current_node: Current node being visited.
            data: Data to search for.

        Returns:
            True if the node is found, False otherwise.
        """
        if current_node is None:
            return False

        if data == current_node.data:
            return True
        elif data < current_node.data:
            return self._search_recursive(current_node.left, data)
        else:
            return self._search_recursive(current_node.right, data)

    def _get_height(self, node):
        """
        Get the height of a node in the AVL tree.

        Args:
            node: Node to get the height of.

        Returns:
            Height of the node.
        """
        if node is None:
            return 0
        return node.height

    def _get_balance_factor(self, node):
        """
        Get the balance factor of a node in the AVL tree.

        Args:
            node: Node to get the balance factor of.

        Returns:
            Balance factor of the node.
        """
        if node is None:
            return 0
        return self._get_height(node.left) - self._get_height(node.right)

    def _get_min_node(self, node):
        """
        Get the node with the minimum value in the AVL tree.

        Args:
            node: Node to start the search from.

        Returns:
            Node with the minimum value.
        """
        current = node
        while current.left is not None:
            current = current.left
        return current

    def _display(self):
        """
        Returns a string representation of the AVL tree.

        Returns:
            String representation of the AVL tree.
        """
        if self.root is None:
            return "Empty AVL Tree"

        lines, *_ = self._display_helper(self.root)
        return "\n".join(lines)

    def _display_helper(self, node):
        """
        Helper method to construct the string representation of the AVL tree.

        Args:
            node: Current node being visited.

        Returns:
            Lines representing the AVL tree, along with the width, height, and middle index.
        """
        if node.right is None and node.left is None:
            line = str(node)
            width = len(line)
            height = 1
            middle = width // 2
            return [line], width, height, middle

        if node.right is None:
            lines, n, p, x = self._display_helper(node.left)
            s = str(node)
            u = len(s)
            first_line = (x + 1) * " " + (n - x - 1) * "_" + s
            second_line = x * " " + "/" + (n - x - 1 + u) * " "
            shifted_lines = [line + u * " " for line in lines]
            return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2

        if node.left is None:
            lines, n, p, x = self._display_helper(node.right)
            s = str(node)
            u = len(s)
            first_line = s + x * "_" + (n - x) * " "
            second_line = (u + x) * " " + "\\" + (n - x - 1) * " "
            shifted_lines = [u * " " + line for line in lines]
            return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2

        left, n, p, x = self._display_helper(node.left)
        right, m, q, y = self._display_helper(node.right)
        s = str(node)
        u = len(s)
        first_line = (x + 1) * " " + (n - x - 1) * "_" + s + y * "_" + (m - y) * " "
        second_line = x * " " + "/" + (n - x - 1 + u + y) * " " + "\\" + (m - y - 1) * " "
        if p < q:
            left += [n * " "] * (q - p)
        elif q < p:
            right += [m * " "] * (p - q)
        zipped_lines = zip(left, right)
        lines = [first_line, second_line] + [a + u * " " + b for a, b in zipped_lines]
        return lines, n + m + u, max(p, q) + 2, n + u // 2

    def __str__(self):
        """
        Returns a string representing the AVL tree.

        Returns:
            A string representing the AVL tree.
        """
        return self._display()

    def __repr__(self):
        """
        Returns a string that represents a valid Python expression to recreate the AVL tree.

        Returns:
            A string that represents a valid Python expression.
        """
        if self.root is None:
            return "Empty AVL Tree"
        return f"AVLTree(root={self.root})"


if __name__ == "__main__":
    # Create a new AVL tree
    avl_tree = AVLTree()

    # Insert nodes into the AVL tree
    avl_tree.insert(30)
    avl_tree.insert(20)
    avl_tree.insert(40)
    avl_tree.insert(10)
    avl_tree.insert(25)
    avl_tree.insert(35)
    avl_tree.insert(50)
    avl_tree.insert(5)
    avl_tree.insert(15)
    # for i in range(51, 300, 30):
    #     avl_tree.insert(i)

    # Print the AVL tree
    print("AVL Tree:")
    print(avl_tree)
    # Output:
    # AVL Tree:
    #                             ___________Node(30)____________
    #                            /                               \
    #             ___________Node(20)____                 ___Node(40)____
    #            /                       \               /               \
    #     ___Node(10)____            Node(25)        Node(35)        Node(50)
    #    /               \
    # Node(5)        Node(15)


    # Delete a node from the AVL tree
    avl_tree.delete(35)

    # Print the AVL tree after deletion
    print("AVL Tree after deletion:")
    print(avl_tree)
    # Output:
    # AVL Tree after deletion:
    #                             ___________Node(30)____
    #                            /                       \
    #             ___________Node(20)____            Node(40)____
    #            /                       \                       \
    #     ___Node(10)____            Node(25)                Node(50)
    #    /               \
    # Node(5)        Node(15)

    # Search for a node in the AVL tree
    data = 25
    is_found = avl_tree.search(data)
    print(f"Node {data} found: {is_found}")
    # Output:
    # Node 25 found: True

    data = 35
    is_found = avl_tree.search(data)
    print(f"Node {data} found: {is_found}")
    # Output:
    # Node 35 found: False
